package top.likeqc.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/** @see <a href="https://leetcode.cn/problems/generate-parentheses">22. 括号生成</a> */
public class GenerateParentheses{
    public static void main(String[] args) {
        Solution solution = new GenerateParentheses().new Solution();
    }
//leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<String> ans = new ArrayList<>();
        public List<String> generateParenthesis(int n) {
            getParenthesis("", n, n);
            return ans;
        }
        
        // 剩余左括号应该小于等于右括号
        private void getParenthesis(String str, int left, int right) {
            if (left == 0 && right == 0) {
                ans.add(str);
                return;
            }
            if (left == right) {
                getParenthesis(str + "(", left - 1, right);
            } else if (left < right) {
                if (left > 0) {
                    getParenthesis(str + "(", left - 1, right);
                }
                getParenthesis(str + ")", left, right - 1);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}